package com.study.algorithm.sort;

import java.util.Arrays;

/**
 * 选择排序。
 *
 * <p><B>排序原理：</B>
 * <ol>
 *   <li>每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其它索引处的值依次进行比较，如果当前索引处的值大于其它某个索引处的值，
 *   则假定其它索引处的值为最小值，最后可以找到最小值所在的索引。</li>
 *   <li>交换第一个索引处和最小值所在的索引处的值。</li>
 * </ol>
 *
 * <p><B>时间复杂度分析：</B>选择排序使用了双层for循环，其中外层循环完成了数据交换，内层循环完成了数据比较，
 * 所以我们分析统计数据交换次数和数据比较次数。
 *
 * <p>数据比较次数：{@code (N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2}，
 * 数据交换次数：{@code N-1}，时间复杂度：{@code N^2/2-N/2+（N-1）=N^2/2+N/2-1}。
 * 根据大O推导法则，保留最高阶项，去除常数因子，时间复杂度为 <B>O(N^2)</B>。
 *
 * @author chenganbang
 */
public class Selection implements Sort {

  private Selection() {
  }

  private static class Holder {
    private static final Selection INSTANCE = new Selection();
  }

  public static Selection getInstance() {
    return Selection.Holder.INSTANCE;
  }

  /**
   * 对数组 a 进行排序。
   *
   * <p>假设待排序数组：[4, 6, 8, 7, 9, 2, 10, 1]，那么排序过程如下：
   * <ul>
   * <li>第 1 趟排序结果（1和4交换）：[<B>1</B>, 6, 8, 7, 9, 2, 10, 4]
   * <li>第 2 趟排序结果（2和6交换）：[1, <B>2</B>, 8, 7, 9, 6, 10, 4]
   * <li>第 3 趟排序结果（4和8交换）：[1, 2, <B>4</B>, 7, 9, 6, 10, 8]
   * <li>第 4 趟排序结果（6和7交换）：[1, 2, 4, <B>6</B>, 9, 7, 10, 8]
   * <li>第 5 趟排序结果（7和9交换）：[1, 2, 4, 6, <B>7</B>, 9, 10, 8]
   * <li>第 6 趟排序结果（8和9交换）：[1, 2, 4, 6, 7, <B>8</B>, 10, 9]
   * <li>第 7 趟排序结果（9和10交换）：[1, 2, 4, 6, 7, 8, <B>9</B>, 10]
   * </ul>
   * 排好序结果：[1, 2, 4, 6, 7, 8, 9, 10]
   *
   * @param source
   *     数组 source
   */
  @Override
  public void sort(Comparable[] source) {
    System.out.println("待排序数组：" + Arrays.toString(source));

    SortHelper sortHelper = SortHelper.getInstance();
    for (int i = 0; i < source.length - 1; i++) {
      int minIndex = i;
      for (int j = i + 1; j < source.length; j++) {
        if (sortHelper.greater(source[minIndex], source[j])) {
          minIndex = j;
        }
      }
      sortHelper.exchange(source, i, minIndex);
      sortHelper.printArray(i + 1, source);
    }

    System.out.println("排好序结果：" + Arrays.toString(source));
  }
}